package me.shan.leet.code;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/can-make-palindrome-from-substring/">构建回文串检测</a>
 *
 * @author liuchuang
 * @version 1.0
 * @since 2023/6/15 11:21
 */
public class T1177PaliQueries {

    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        List<Boolean> result = new ArrayList<>(queries.length);
        int n = s.length();
        int[] count = new int[n + 1];
        for (int i = 0; i < n; i++) {
            count[i + 1] = count[i] ^ (1 << (s.charAt(i) - 'a'));
        }
        for (int[] query : queries) {
            int l = query[0], r = query[1], k = query[2];
            int bits = 0, temp = count[l] ^ count[r + 1];
            while (temp > 0) {
                temp &= temp - 1;
                bits++;
            }
            result.add(bits / 2 <= k);
        }
        return result;
    }

    public static void main(String[] args) {
        T1177PaliQueries p = new T1177PaliQueries();
        System.out.println(p.canMakePaliQueries("abcda",
                new int[][]{{3, 3, 0}, {1, 2, 0}, {0, 3, 1}, {0, 3, 2}, {0, 4, 1}}));
    }

}
